﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<set>
using namespace std;

//set底层是红黑树，而红黑树就是平衡版本的禁止值冗余的搜索二叉树，
//其迭代器为双向迭代器。
//set的使用需要包含set头文件，其接口与之前的STL容器有许多相似，
//因此这里只会对一些较特殊的基础接口进行介绍


//set的初始化操作支持使用迭代器区间及{}，但不支持(val)初始化
void test1()
{
	//set<int> s(1);不支持
	set<int> s1{ 4,67,69,234,78,3,8,0,1,4 };//{}初始化
	set<int> s2(s1.begin(), s1.end());//迭代器区间初始化
}

//set的迭代器顺序是按照中序遍历来的，也就是说，使用迭代器遍历set，
//其行为为将一组数据去重排序，且默认仿函数使用less，所以默认升序排序
void test2()
{
	set<int> s{ 7,5,3,8,9,1,2,5,6,4 };
	for (const auto& e : s)
	{
		cout << e << " ";//1 2 3 4 5 6 7 8 9\n->去除了重复数据5，并对其他数据进行了升序排序
	}
	cout << endl;
}

//insert与erase：两接口的返回值根据重载函数有所差异，但需注意
//size_type erase (const value_type& val);其返回值为删除的元素个数
//*注意由于set底层是红黑树，于插入操作而言，迭代器很稳定，基本不会出现迭代器失效的问题*
//*但erase的迭代器相关重载无论删除的是否为根，都会造成迭代器失效问题*

//由于set本身行为是无重复排序，所以可能会疑惑insert的作用，为什么不直接写成push呢？参数为什么还需要迭代器呢？
//其实insert参数的迭代器可以帮助底层快速找到符合搜索二叉树的正确位置，提升效率（即插入提示）

//关于erase的一个函数重载的返回值为删除数量，而不为bool的原因：实际上，这是为了契合multiset（允许重复数据的搜索二叉树）
//中的erase函数，同时，set返回值设置为删除数量其实也能起到类似bool的作用
void test3()
{
	//insert
	set<int> s{ 7,5,3,8,9,1,2,5,6,4 };
	for (const auto& e : s)
	{
		cout << e << " ";//1 2 3 4 5 6 7 8 9\n
	}
	cout << endl;
	s.insert(s.begin(), 99);
	for (const auto& e : s)
	{
		cout << e << " ";//1 2 3 4 5 6 7 8 9 99\n
	}
	cout << endl;
	//验证insert失效问题
	auto iz = s.begin();
	s.insert(iz, 999);
	cout << "*iz: " << *iz << endl;//1->迭代器未失效

	//erase
	cout << s.erase(888) << endl;//数据中没有888，所以返回值为0
	for (const auto& e : s)
	{
		cout << e << " ";//1 2 3 4 5 6 7 8 9 99\n
	}
	cout << endl;

	cout << s.erase(99) << endl;//数据中存在99，所以返回值为1
	for (const auto& e : s)
	{
		cout << e << " ";//1 2 3 4 5 6 7 8 9\n
	}
	cout << endl;

	//验证erase迭代器参数重载函数的迭代器失效
	/*auto is = s.begin();
	s.erase(is);
	cout << "*is: " << *is << endl;*///断言报错->调用单迭代器参数erase重载函数后迭代器失效
	auto it = s.begin();
	auto ift = ++s.begin();
	s.erase(it, ift);
	//cout << "*it: " << *it;//断言报错-》第一个迭代器失效
	cout << "ift: " << *ift << endl;//正常运行->由于左闭右开，所以最后一个迭代器不失效
}


//find与erase函数
//find函数没有重载函数，其函数原型为iterator find (const value_type& val) const;
//查找成功则返回数据对应的迭代器，查找失败返回end迭代器，因此，
//判断是否成功查找只需要将返回值与end迭代器进行比较即可
void test4()
{
	set<int> s{ 7,5,3,8,9,1,2,5,6,4 };
	if (s.find(888) != s.end())
	{
		cout << "查找成功！" << endl;
	}
	else {
		cout << "查找失败！" << endl;//查找失败！-》数据中没有888，因此最终返回值==end，即查找失败
	}

	if (s.find(1) != s.end())
	{
		cout << "查找成功！" << endl;//查找成功！
	}
	else {
		cout << "查找失败！" << endl;
	}
	

	//erase具备参数为迭代器的重载函数，可配合find函数使用
	//注：可以将参数为val的erase重载底层理解为参数为迭代器的重载+find函数
	auto i = s.find(1);
	if (i != s.end())
	{
		s.erase(i);
	}
	for (const auto& e : s)
	{
		cout << e << " ";//2 3 4 5 6 7 8 9\n-》查找完毕，成功删除
	}
	cout << endl;
}


//upper_bound与lower_bound接口
//upper_bound函数原型为iterator upper_bound(const value_type& val) const;
//其作用是返回>=val的迭代器
// 
//lower_bound函数原型为iterator lower_bound (const value_type& val) const;
//其作用是返回>val的迭代器
//
//这两个函数乍一看似乎很奇怪，没什么实际用途，实际上，这两个函数很巧妙
//可以通过它们配合erase的参数为迭代器区间的重载函数实现set中数据区间的删除
//（注：STL中接受两个迭代器参数的erase重载函数，操作的区间是左闭右开 [first, last)​​）
//举例来说，比如要删除1~99的数据，就lower_bound(1),upper_bound(99)，然后调用erase函数的迭代器区间重载版本即可
void test5()
{
	set<int> s{ 7,5,3,8,9,1,2,5,6,4 ,231,52,643,6643,84,452,95 };
	for (const auto& e : s)
	{
		cout << e << " ";//1 2 3 4 5 6 7 8 9 52 84 95 231 452 643 6643
	}
	cout << endl;

	//尝试使用上述三个接口实现删除1~9区间上的数据
	auto i1 = s.lower_bound(1);//返回>=1的迭代器
	auto i2 = s.upper_bound(9);//返回>9的迭代器
	s.erase(i1, i2);//左闭右开，删除>=1且<=9的数据
	for (const auto& e : s)
	{
		cout << e << " ";//52 84 95 231 452 643 6643
	}
	cout << endl;
}

int main()
{
	//test1();
	//test2();
	test3();
	//test4();
	//test5();
	return 0;
}